package binaryTree;
/*
* KY11 二叉树遍历
* 描述
* 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
* 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
* 建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
* 输入描述：
* 输入包括1行字符串，长度不超过100。
* 输出描述：
* 可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，
* 每个字符后面都有一个空格。 每个输出结果占一行。
*/
import java.util.Scanner;
public class Main {
    //二叉树的节点
    static class TreeNode{
        private char val;           //结点的值
        private TreeNode left;      //左子树
        private TreeNode right;     //右子树
        //构造函数
        public TreeNode(char val){
            this.val = val;
        }
    }
    public static int index = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        TreeNode root = null;
        while (in.hasNext()) { // 注意 while 处理多个 case
            String s = in.next();
            index = 0;  //每一组输入后要重置下标为0
            root = creatBinaryTree(s);  //创建二叉树
            inOrder(root);  //中序打印二叉树
            System.out.println();
        }
    }
    //创建二叉树
    public static TreeNode creatBinaryTree(String s){
        char c = s.charAt(index);
        if(c == '#'){
            return null;
        }
        //创建根结点
        TreeNode root = new TreeNode(c);
        index++;
        //创建左子树
        root.left = creatBinaryTree(s);
        index++;
        //创建右子树
        root.right = creatBinaryTree(s);
        //返回创建的二叉树
        return root;
    }
    //中序打印二叉树
    private static void inOrder(TreeNode root){
        if(root == null){
            return;
        }

        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}